import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    private int[] index = new int[1];

    public BTNode createBT(String str) {
        index[0] = 0; // 重置索引
        return createBTRecursive(str);
    }

    public BTNode createBTRecursive(String str) {
        if (index[0] >= str.length() || str.charAt(index[0]) == ' ') {
            index[0]++;
            return null;
        }
        if (str.charAt(index[0]) == '(') {
            index[0]++;
        }
        if (str.charAt(index[0]) == ',') {
            index[0]++;
        }
        if (str.charAt(index[0]) == ')') {
            index[0]++;
            return null;
        }
        char data = str.charAt(index[0]++);
        BTNode node = new BTNode(data);
        node.lchild = createBTRecursive(str);
        node.rchild = createBTRecursive(str);
        if (index[0] < str.length() && str.charAt(index[0]) == ')') {
            index[0]++;
        }
        return node;
    }

        public List<Character> inorderTraversal(BTNode root) {
            List<Character> result = new ArrayList<>();
            inorderRecursive(root, result);
            return result;
        }

        private void inorderRecursive(BTNode node, List<Character> result) {
            if (node != null) {
                inorderRecursive(node.lchild, result);
                result.add(node.data);
                inorderRecursive(node.rchild, result);
            }
        }

        public char[] findChild(BTNode root, char target) {
            char[] children = new char[]{'#', '#'}; // 初始化：无孩子标记为'#'
            findChildRecursive(root, target, children);
            return children;
        }

        private void findChildRecursive(BTNode node, char target, char[] children) {
            if (node == null) return;
            if (node.data == target) {
                if (node.lchild != null) {
                    children[0] = node.lchild.data;
                }
                if (node.rchild != null) {
                    children[1] = node.rchild.data;
                }
                return;
            }
            findChildRecursive(node.lchild, target, children);
            findChildRecursive(node.rchild, target, children);
        }

        public int getHeight(BTNode root) {
            if (root == null) return 0;
            int leftHeight = getHeight(root.lchild);
            int rightHeight = getHeight(root.rchild);
            return Math.max(leftHeight, rightHeight) + 1;
        }

        public void freeBT(BTNode root) {
            if (root != null) {
                freeBT(root.lchild);
                freeBT(root.rchild);
                root.lchild = null;
                root.rchild = null;
            }
        }
    }
